//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
//
// Related Topics 数组 二分查找 分治 👍 7403 👎 0

package leetcode.editor.cn;

/**
 * @author Leunghan
 * @date 2025-02-23 23:32:36
 */
class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();

        System.out.println(solution.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len = nums1.length + nums2.length;
            if (len % 2 == 0) {
                return (getKthElement(nums1, nums2, len / 2) + getKthElement(nums1, nums2, len / 2 + 1)) / 2.0;
            }
            return getKthElement(nums1, nums2, len / 2 + 1);
        }

        public int getKthElement(int[] nums1, int[] nums2, int k) {
            int index1 = 0, index2 = 0;
            int len1 = nums1.length, len2 = nums2.length;

            while (true) {
                if (index1 == len1) {
                    return nums2[index2 + k - 1];
                }
                if (index2 == len2) {
                    return nums1[index1 + k - 1];
                }
                if (k == 1) {
                    return Math.min(nums1[index1], nums2[index2]);
                }

                int half = k / 2;
                int nIndex1 = Math.min(len1, index1 + half) - 1;
                int nIndex2 = Math.min(len2, index2 + half) - 1;
                if (nums1[nIndex1] < nums2[nIndex2]) {
                    k = k - (nIndex1 - index1 + 1);
                    index1 = nIndex1 + 1;
                } else {
                    k = k - (nIndex2 - index2 + 1);
                    index2 = nIndex2 + 1;
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}